// https://www.lintcode.com/problem/group-anagrams/description
// 772. 错位词分组
// 给一字符串数组, 将 错位词(指相同字符不同排列的字符串) 分组

// 样例
// 给出 strs = ["eat", "tea", "tan", "ate", "nat", "bat"],
// 返回 
// [
//     ["ate", "eat","tea"],
//     ["nat","tan"],
//     ["bat"]
// ]
// 注意事项
// 所有的输入均为小写字母



class Solution {
public:
    /**
     * @param strs: the given array of strings
     * @return: The anagrams which have been divided into groups
     */
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        vector<vector<string>> result;
        map<string, vector<string>> record_map;
        // ["eat","tea","tan","ate","nat","bat","eaaet"] 不能用set作为key，不能去重

        for (string s: strs)
        {
            string key = s;
            sort(key.begin(), key.end());
            record_map[key].push_back(s);
        }
        for (map<string, vector<string>>::iterator it = record_map.begin(); it != record_map.end(); ++it)
        {
            result.push_back(it->second);
        }
        return result;
    }
};